home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Magnum One
/
Magnum One (Mid-American Digital) (Disc Manufacturing).iso
/
d12
/
snip9_91.arc
/
LASORT.C
< prev
next >
Wrap
C/C++ Source or Header
|
1991-09-17
|
12KB
|
238 lines
/*********************************************************************/
/* */
/* This Program Written by Paul Edwards. */
/* */
/*********************************************************************/
/*********************************************************************/
/* */
/* licorice all sort - an O(N) sort program. Version 1.31 */
/* */
/* This program takes the following parameters: */
/* 1) base - A pointer to the start of your data */
/* 2) n - number of elements to be sorted */
/* 3) size - size of elements being sorted */
/* 4) offset - number of bytes into the record */
/* */
/* Designed to be much like C's builtin qsort, this program sorts */
/* into ascending order an array base[0]...base[n-1] of objects */
/* size size. (not a typo). */
/* */
/* After my last aborted attempt at creating an original sort */
/* program, here is a new one. It is called lasort, short for */
/* licorice all sort. */
/* */
/* To sort an array of character strings, you first start off */
/* looking at the first byte. You create a table of statistics */
/* (UCHAR_MAX entries) so that you know how many A's ther are etc. */
/* */
/* It then once again traverses the list, knowing where to put */
/* each element that is out of order. */
/* */
/* This code is dedicated to the public domain. Do with it what */
/* you will, but seeing as I invented it, it shall be known */
/* hereafter as licorice all sort, and not by any other name. */
/* The unusual name was suggested by my father, who preferred it */
/* to death sort. Also, a catchy name helps to make a sort */
/* popular (ala bubble sort). */
/* */
/* If you would like to contact me about this program, I normally */
/* hang out on a bulletin board called Paragon, in Sydney, */
/* Australia. Fidonet address: 3:712/502 */
/* */
/* licorice - I don't like it either. */
/* */
/* Written on 03-Oct-1989. */
/* */
/* Copyright 1989 Paul Edwards. */
/* */
/* Dedicated to my American friend Dan Malcolm, convinced */
/* that Australians never write public domain software <grin>. */
/* */
/* Version 1.3 enhancement. When you have less than or equal to */
/* RETIME records to sort, use Radix Exchange Sort instead. */
/* When you have less than or equal to INTIME records to sort, use */
/* Insertion Sort instead. */
/* */
/* Version 1.31 fixed up void *, char *, unsigned char * */
/* */
/*********************************************************************/
/* RETIME, INTIME are machine dependant, find values that suit you */
/* best. List of possible optimum times for different machines: */
/* IBM XT compatible: RETIME 46, INTIME 7 */
#define RETIME 46 /* when radix is better than licorice */
#define INTIME 7 /* when insertion sort is better than resort */
#define MAX 300 /* maximum length of strings to be sorted */
static char temp[MAX]; /* temporary storage for swap */
#include <string.h>
#include <limits.h>
#include <assert.h>
#include <stdlib.h>
/*********************************************************************/
/* */
/* insertion sort - start from the bottom element (which is a */
/* sorted array of length 1), then every time you move up one */
/* element, you move it down (swapping with all elements below it) */
/* until it is in its sorted position. */
/* */
/*********************************************************************/
void insort(void *base, int n, int size, int offset)
{
register int j,rc,i;
for (i=0;i<n;i++) /* moving up one element */
{
for (j=i;j>0;j--) /* move down until in sorted order */
{
rc = memcmp((unsigned char *)base+j*size+offset,
(unsigned char *)base+(j-1)*size+offset,size-offset);
if (rc < 0)
{
/* swapping elements along the way */
memcpy(temp,(unsigned char *)base+j*size,size);
memcpy((unsigned char *)base+j*size,
(unsigned char *)base+(j-1)*size,size);
memcpy((unsigned char *)base+(j-1)*size,temp,size);
}
else break;
}
}
return;
}
/*********************************************************************/
/* */
/* radix exchange sort. view one bit at a time, getting all '1' */
/* bits up the top, and all the '0' bits down the bottom. */
/* */
/*********************************************************************/
void resort(void *base, int n, int size, int offset)
{
int bytesin; /* no of bytes into the string */
int bitsin; /* no of bits into the byte */
int p; /* bottom element number */
int q; /* top element number */
register unsigned char mask = 0x80; /* bit we are interested in */
if (n <= 1) return; /* we have finished this sub-sort if we have
one or less elements to sort */
bytesin = offset / CHAR_BIT; /* work out how many bytes we are
into the element by dividing by the number of bits we are
into the element by the number of bits in a byte */
if (bytesin == size) return; /* we have just passed the length of the
data */
bitsin = offset % CHAR_BIT; /* no of bits into the byte */
mask = mask >> bitsin; /* mask masks the bit we are interested in */
p = 0; /* low element starts at 0 */
q = n-1; /* high element starts at n-1 */
while (p <= q) /* until all swaps have been done */
{
while (((*((unsigned char *)base+p*size+bytesin) & mask) == 0)
&& (p < n)) p++; /* p will move up until it finds a bit that
is not 0 (or until it reaches the top) */
/* q moves down until if finds a bit that is 0
(or until it reaches the bottom) */
while ((q >= 0) &&
((*((unsigned char *)base+q*size+bytesin) & mask) != 0)) q--;
if (p < q) /* p has a 1 bit and q has a 0 bit, so swap */
{
memcpy(temp,(unsigned char *)base+p*size,size);
memcpy((unsigned char *)base+p*size,
(unsigned char *)base+q*size,size);
memcpy((unsigned char *)base+q*size,temp,size);
p++; /* p now points to a 0 bit, so move up one more */
q--; /* q now points to a 1 bit, so move down one more */
}
}
/* sort lower numbers */
if (p <= INTIME) insort(base,p,size,(offset+1)/CHAR_BIT);
else resort((unsigned char *)base,p,size,offset+1);
/* sort higher numbers */
if ((n-p) <= INTIME)
insort((unsigned char *)base+p*size,n-p,size,(offset+1)/CHAR_BIT);
else resort((unsigned char *)base+p*size,n-p,size,offset+1);
return;
}
void lasort(void *base, int n, int size, int offset)
{
int *stats; /* ptr to table of statistics (how many A's etc) */
unsigned char **subp; /* table of pointers to top of characters */
unsigned char **orgp; /* table of original pointers */
register int i; /* used for many things */
register unsigned char critic; /* character to be sorted */
register unsigned char *wereat; /* pointer to element we're up to */
assert((stats = malloc((UCHAR_MAX+1)*sizeof(*stats))) != NULL);
assert((subp = malloc((UCHAR_MAX+1)*sizeof(*subp))) != NULL);
assert((orgp = malloc((UCHAR_MAX+1)*sizeof(*orgp))) != NULL);
for (i=0;i<(UCHAR_MAX+1);i++) stats[i] = 0; /* reset statistics */
for (i=0;i<n;i++) /* create stats */
stats[*((unsigned char *)base+i*size+offset)]++;
orgp[0] = subp[0] = base;
/* create table of original pointers, and subpointers */
for (i=0;i<UCHAR_MAX;i++)
orgp[i+1] = subp[i+1] = subp[i] + size * stats[i];
for (i=0;i<n;)
{
/* start at bottom of table */
wereat = (unsigned char *)base+i*size;
critic = *(wereat+offset); /* byte to put in sorted order */
if (wereat >= orgp[critic]) i++; /* is it already sorted? */
else
{
memcpy(temp,wereat,size); /* copy the record into temp */
memcpy(wereat,subp[critic],size); /* get unsorted back here */
memcpy(subp[critic],temp,size); /* put temp into sorted order */
subp[critic]+=size; /* next pointer will be one record up */
}
}
free(subp); /* don't need table of subpointers any more */
if (++offset < size) /* if there are still more bytes in record */
{
for (i=0;i<(UCHAR_MAX+1);i++)
{
/* if there are sub-records of a character, sort them */
if (stats[i] > 1)
{
/* if there are less than INTIME records, use insort */
if (stats[i] <= INTIME) insort(orgp[i],stats[i],size,offset);
/* else if there are less than RETIME records, use resort */
else if (stats[i] <= RETIME)
resort(orgp[i],stats[i],size,offset*8);
else lasort(orgp[i],stats[i],size,offset);
}
}
}
free(stats); /* don't need table of statistics anymore */
free(orgp); /* don't need table of original pointers either */
return;
}
/* example of program that calls licorice all sort */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
main(int argc,char **argv)
{
FILE *fp,*fq;
time_t t1,t2;
int numrec,lenrec;
char *myarr;
if (argc < 5)
{
printf("you must enter input file name, output file name\n");
printf("number of elements to read, length of elements\n");
printf("without making any mistakes\n");
return (1);
}
assert((fp = fopen(*(argv+1),"rb")) != NULL);
assert((fq = fopen(*(argv+2),"wb")) != NULL);
assert((numrec = atoi(*(argv+3))) != 0);
assert((lenrec = atoi(*(argv+4))) != 0);
assert((myarr = malloc(lenrec*numrec)) != NULL);
numrec = fread(myarr,lenrec,numrec,fp);
printf("%d records read in to licorice all sort\n",numrec);
time(&t1);
lasort((unsigned char *)myarr,numrec,lenrec,0);
time(&t2);
printf("licorice all sort took %d secs to process %d records\n",
(int)difftime(t2,t1),numrec);
fwrite(myarr,lenrec,numrec,fq);
return (0);
}